class Solution {
public:
    map<char, string> rec;
    void getRes(string& digits, string cur, vector<string>& res, int start) {
        if (start >= digits.size()) {
            res.push_back(cur);
            return;
        }
        for (int j = 0; j < rec[digits[start]].size(); ++j) {
            cur.push_back(rec[digits[start]][j]);
            getRes(digits, cur, res, start + 1);
            cur.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.empty()) return res;
        rec['1'] = "";
        rec['2'] = "abc";
        rec['3'] = "def";
        rec['4'] = "ghi";
        rec['5'] = "jkl";
        rec['6'] = "mno";
        rec['7'] = "pqrs";
        rec['8'] = "tuv";
        rec['9'] = "wxyz";
        string cur = "";
        getRes(digits, cur, res, 0);
        return res;
    }
};